package 牛客题霸;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 给出一组区间，请合并所有重叠的区间。
 * 请保证合并后的区间按区间起点升序排列。
 * <p>
 * [[10,30],[20,60],[80,100],[150,180]]
 * 返回值：
 * [[10,60],[80,100],[150,180]]
 */
public class 合并区间 {

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> dum = new ArrayList<>();
        if (intervals == null || intervals.size() <= 0) {
            return dum;
        }
        Collections.sort(intervals, (o1, o2) -> o1.start - o2.start);
        int newStart = intervals.get(0).start;
        int newEnd = intervals.get(0).end;
        for (Interval inter : intervals) {
            if (inter.start <= newEnd && inter.end > newEnd) {
                newEnd = inter.end;
            }
            if (inter.end > newEnd) {
                dum.add(new Interval(newStart, newEnd));
                newStart = inter.start;
                newEnd = inter.end;
            }
        }
        dum.add(new Interval(newStart, newEnd));
        return dum;
    }

    public static void main(String[] args) {

    }

    public class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }
}
